package Other;

import java.util.*;

/**
 * @author:gao
 * @date:2020/7/9
 * @time:18:31
 * @version:0.0.1
 * @description:none
 */


//142. 环形链表 II
public class DetectCycle {
}

class ListNode {
    int val;
    ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
 }

//用set保存
class Solution009 {
    public ListNode detectCycle(ListNode phead) {
        ListNode head = phead;
        Set<ListNode> set = new HashSet<>();
        int i=0;
        while (head!=null){
            if(set.contains(head)){
                return head;
            }else{
                set.add(head);
            }
            head=head.next;
        }
        return null;
    }
}

//快慢指针
class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast)break;
        }
        if(fast==slow&&fast!=null&&fast.next!=null) {
            ListNode p = head;
            while (p != slow) {
                p = p.next;
                slow = slow.next;
            }
            return p;
        }
        return null;
    }
}

